A packet switching network comprises a plurality of nodes interconnected by links. Typically, the packet switching network supports a plurality of connections, each of which interconnects and transmits packets between a source node and a destination node.
Telecommunications services differ greatly in their tolerance of packet losses and packet delays. In an integrated services packet network, some of the applications, such as most forms of data communications, are not delay-sensitive but may have stringent loss requirements. The lack of delay sensitivity, however, permits the recovery of packet losses through retransmission. Other applications, such as interactive voice and video, involve real-time traffic and require delivery of their packets within a short period of time. These delay sensitive applications have various degrees of loss sensitivity as well. Unfortunately, packet loss recovery through retransmission typically is not fast enough to be useful in the case of delay sensitive traffic. Therefore, alternative strategies for preventing packet losses need to be utilized for these types of traffic.
The above-identified patent applications describe a congestion free transmission strategy for a connection oriented packet network. The congestion free transmission strategy guarantees a bounded end-to-end delay for any packet being transmitted from a source node to destination node of a connection. This transmission strategy is also loss free in that buffer overflow at the network nodes is eliminated. (See also U. Mukherji, A Schedule-Based Approach For Flow Control In Data Communication Networks, PhD thesis, MIT, Dept. of Electrical Engineering and Computer Science, Cambridge, Mass., 1986; Rene, L. Cruz, "Maximum Delay in Buffered Multistage Interconnection Networks," Proceedings Of The INFOCOM, pp 135-144, New Orleans, La., March 1988; C. K. Kim, S. H. Lee, and L. T. Wu, "Circuit Emulations," International Journal Of Digital And Analog Cable Systems, 1988, pp 245-256; and P. M. Gopal and Bharath Kadaba, "Network Delay Considerations for Packetized Voice," Performance Evaluation, Vol. 9, pp 167-180, July 1989, for other transmission schemes which offer bounded end-to-end delay).
The congestion free transmission strategy of the above-identified patent applications is composed of two parts. A packet admission policy is imposed for each connection at its source node (i.e. a policy which controls the admission of packets for each connection into the network) and a queuing discipline is imposed at the network nodes.
In the congestion free transmission strategy of the above-identified patent applications, packets may be viewed as being transmitted between nodes via internal links in time frames. Thus, on each internal link in the network, successive time intervals or frames of duration T are defined. These frames may be viewed as logical containers which propagate from the transmitting end to the receiving end of a link. Similarly, packets for a particular connection may be viewed as entering the network from the outside world at a source node of the connection via an access link. Successive time frames of duration T may also be defined for the access links.
The admission policy for packets belonging to a particular connection k is that an upper limit is imposed on the aggregate length of packets admitted to the network for the particular connection k at its source node during each frame. More particularly, if the time frames have a duration T, the aggregate length of packets which can be admitted to the network for the connection k via an access link at its source node is r.sub.k T where r.sub.k is a transmission bandwidth allocated to the connection k. The bandwidth r.sub.k is allocated to a connection k such that the sum of the rates allocated to the connections traversing each link in the network do not exceed the capacity of that link. This packet admission policy amounts to imposing a smoothness requirement on the packet stream of a connection at its source node. (In the absence of such an admission policy, packets of a packet stream may enter the network in dense burst).
The queuing policy which is utilized at the network nodes in the congestion free transmission strategy of the above-identified patent applications is as follows. A packet which arrives at a node on a given incoming link in a specific arriving time frame is delayed at the node at least until the specific arriving frame expires and is transmitted o the appropriate outgoing link in the first departing frame which starts after the specific arriving frame expires. This queuing policy serves to maintain the smoothness of each connection in the network over each link traversed by a connection.
As the packet stream of each connection over each link traversed by a connection is maintained as smooth, there is no congestion in the network. Thus in the congestion free transmission strategy of the above-identified patent applications, packet losses are eliminated and a guaranteed end-to-end delay for each packet of each connection is achieved.
While the congestion free transmission strategy of the above-described patent applications has significant advantages (i.e. guaranteed bounded end-to-end packet transmission delays and elimination of packet losses), the above-described congestion free transmission strategy does suffer from a shortcoming in that it results in an under-utilized network. The reason is that while there is a maximum limit imposed on the aggregate length of packets which can be admitted to the network at the source node of each connection during a time frame of duration T, the reality is that in many time frames, packets with less than this aggregate length will be admitted.
Accordingly, it is an object of the present invention to modify the above-described congestion free transmission strategy to increase network utilization.
Improvement of network utilization in the presence of bursty packet traffic takes place through the process of statistical multiplexing, which tends to average out the statistical fluctuations of individual traffic streams. However, statistical multiplexing is responsible for two service impairments. These are packet losses and increased packet delay. As indicated previously, the degree of tolerance of various telecommunications services with respect to packet loss and packet delay is widely different.
In a conventional statistical multiplexing process it is possible to roughly distinguish between two elements, both of which contribute to an overall multiplexing gain. The two elements are averaging the traffic over different connections and averaging over time. When a number of packet streams are added up in a multiplexer, the peaks and valleys of the instantaneous transmission rates of the individual streams mix together, forming a smoother aggregated traffic stream, thereby permitting a higher transmissing efficiency. Since this aggregated traffic still has some fluctuations, further multiplexing gain becomes possible by averaging out its fluctuations over time, through a queuing mechanism. If the duration of the time over which traffic averaging takes place is not carefully regulated, this second element of statistical multiplexing can lead into long and, often unpredictable, end-to-end packet transmission delays. (See, e.g. Henning Schulzrinne, James F. Kurose, and Don Towsley, "Congestion Control for Real-Time Traffic in High-Speed Networks," Proceedings Of The INFOCOM, pp 543-550, San Francisco, Calif., June 1990; Chin Yuan and John Silvester, "Queuing Analysis of Delay Constrained Voice Traffic in a Packet Switching System," IEEE Journal On Selected Areas Of Communications, Vol. SAC-7, No. 5, pp 729-738, June 1989; and Bezalel Gavish and Paul Schweitzer, "The Markovian Queue with Bounded Waiting Time," Management Science, Vol. 23, No. 12, pp 1349-1357, August 1977 for some prior art solutions to this problem.)
In view of the foregoing, it is an object of the present invention to provide statistical multiplexing on a limited duration basis and to combine such duration limited statistical multiplexing with the congestion free packet transmission strategy of the above-identified patent applications to achieve 1) the high level network utilization provided by statistical multiplexing, 2) the bounded end-to-end delay guarantees provided by the congestion free transmission strategy, 3) loss free transmission for the part of the traffic with such a requirement, and 4) loss performance for the rest of the traffic on an as needed basis. The combination of the congestion free transmission strategy of the above-identified patent applications and statistical multiplexing is unobvious and has not been achieved heretofore. As is shown below, this combination results in unexpected advantages for the transmission of packets in a packet switching network.
It is also an object of the present invention to provide a transmission strategy for packets in a packet switching network which provides loss and delay guarantees to different forms of traffic on an as needed basis.